package 算法.leetcode.labuladong.数组和链表;

import 算法.leetcode.offer.base.ListNode;

/**
 * @author lchenglong
 * @date 2022/6/16
 */
public class 反转链表 {
    class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null)return head;
            // A -> B -> C -> D
            // A -> reverse(B->C-D)
            ListNode last = reverseList(head.next);
            // A -> B <- C <- D
            //      |
            //      v
            //     null
            // A -> B <- C <- D
            //   <-
            head.next.next = head;
            // null <- A <- B <- C <- D
            head.next = null;
            return last;
        }
    }
}
